// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software 
// for any purpose with or without fee is hereby granted, provided 
// that the above copyright notice and this permission notice appear 
// in all copies. 
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL 
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED 
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE 
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR 
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN      
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 

// This file tests that the library can be used from Rust programs.

mod framework;

use std::ptr;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
use std::cmp::Ordering;

// Traits for comparison and hashing
pub trait Equal<Rhs = Self> {
    fn equal(&self, other: &Rhs) -> bool;
}

pub trait Hashable {
    fn hash(&self) -> u64;
}

// Implementations for specific types
impl Equal for i32 {
    fn equal(&self, other: &i32) -> bool {
        self == other
    }
}

impl Hashable for i32 {
    fn hash(&self) -> u64 {
        let mut hasher = DefaultHasher::new();
        self.hash(&mut hasher);
        hasher.finish()
    }
}

impl Equal for String {
    fn equal(&self, other: &String) -> bool {
        self == other
    }
}

impl Hashable for String {
    fn hash(&self) -> u64 {
        let mut hasher = DefaultHasher::new();
        self.hash(&mut hasher);
        hasher.finish()
    }
}

// Test functions
#[test]
fn test_compare_int() {
    let a = 1;
    let b = 2;
    assert!(!a.equal(&b));

    let a = 2;
    let b = 2;
    assert!(a.equal(&b));
}

#[test]
fn test_compare_string() {
    let s1 = String::from("hello");
    let s2 = String::from("hello");
    let s3 = String::from("world");

    assert!(!s1.equal(&s3));
    assert!(s1.equal(&s2));
}

#[test]
fn test_hash_int() {
    let a = 1;
    let b = 2;
    assert!(a.hash() != b.hash());

    let a = 2;
    let b = 2;
    assert!(a.hash() == b.hash());
}

#[test]
fn test_hash_string() {
    let s1 = String::from("hello");
    let s2 = String::from("hello");
    let s3 = String::from("world");

    assert!(s1.hash() != s3.hash());
    assert!(s1.hash() == s2.hash());
}

// Data structures
struct ArrayList<T> {
    data: Vec<T>,
}

impl<T> ArrayList<T> {
    fn new() -> Self {
        ArrayList { data: Vec::new() }
    }

    fn free(self) {}
}

struct AVLTree<K, V> {
    root: Option<Box<Node<K, V>>>,
}

struct Node<K, V> {
    key: K,
    value: V,
    left: Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>,
    height: i32,
}

impl<K: Ord, V> AVLTree<K, V> {
    fn new() -> Self {
        AVLTree { root: None }
    }

    fn free(self) {}
}

struct BinaryHeap<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> BinaryHeap<T> {
    fn new() -> Self {
        BinaryHeap { data: Vec::new() }
    }

    fn free(self) {}
}

struct BloomFilter {
    bits: Vec<bool>,
    hash_functions: Vec<Box<dyn Fn(&[u8]) -> u64>>,
}

impl BloomFilter {
    fn new(size: usize, hash_functions: Vec<Box<dyn Fn(&[u8]) -> u64>>) -> Self {
        BloomFilter {
            bits: vec![false; size],
            hash_functions,
        }
    }

    fn free(self) {}
}

struct HashTable<K: Hashable + Equal, V> {
    buckets: Vec<Vec<(K, V)>>,
}

impl<K: Hashable + Equal, V> HashTable<K, V> {
    fn new() -> Self {
        HashTable { buckets: Vec::new() }
    }

    fn free(self) {}
}

struct List<T> {
    head: Option<Box<ListNode<T>>>,
}

struct ListNode<T> {
    data: T,
    next: Option<Box<ListNode<T>>>,
}

impl<T> List<T> {
    fn new() -> Self {
        List { head: None }
    }

    fn prepend(&mut self, data: T) {
        let new_node = Box::new(ListNode {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn free(self) {}
}

struct Queue<T> {
    data: Vec<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue { data: Vec::new() }
    }

    fn free(self) {}
}

struct Set<T: Hashable + Equal> {
    data: Vec<T>,
}

impl<T: Hashable + Equal> Set<T> {
    fn new() -> Self {
        Set { data: Vec::new() }
    }

    fn free(self) {}
}

struct SList<T> {
    head: Option<Box<SListNode<T>>>,
}

struct SListNode<T> {
    data: T,
    next: Option<Box<SListNode<T>>>,
}

impl<T> SList<T> {
    fn new() -> Self {
        SList { head: None }
    }

    fn prepend(&mut self, data: T) {
        let new_node = Box::new(SListNode {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    fn free(self) {}
}

struct Trie {
    root: TrieNode,
}

struct TrieNode {
    children: Vec<Option<Box<TrieNode>>>,
    is_end: bool,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode {
                children: vec![None; 256],
                is_end: false,
            },
        }
    }

    fn free(self) {}
}

// Test data structures
#[test]
fn test_arraylist() {
    let arraylist = ArrayList::<i32>::new();
    arraylist.free();
}

#[test]
fn test_avl_tree() {
    let avl_tree = AVLTree::<String, i32>::new();
    avl_tree.free();
}

#[test]
fn test_binary_heap() {
    let heap = BinaryHeap::<i32>::new();
    heap.free();
}

#[test]
fn test_bloom_filter() {
    let filter = BloomFilter::new(16, vec![Box::new(|data: &[u8]| {
        let mut hasher = DefaultHasher::new();
        data.hash(&mut hasher);
        hasher.finish()
    })]);
    filter.free();
}

#[test]
fn test_hash_table() {
    let hash_table = HashTable::<String, i32>::new();
    hash_table.free();
}

#[test]
fn test_list() {
    let mut list = List::<i32>::new();
    list.prepend(1);
    list.prepend(2);
    list.prepend(3);
    list.free();
}

#[test]
fn test_queue() {
    let queue = Queue::<i32>::new();
    queue.free();
}

#[test]
fn test_set() {
    let set = Set::<String>::new();
    set.free();
}

#[test]
fn test_slist() {
    let mut list = SList::<i32>::new();
    list.prepend(1);
    list.prepend(2);
    list.prepend(3);
    list.free();
}

#[test]
fn test_trie() {
    let trie = Trie::new();
    trie.free();
}
